package code1.dp;

/**
 * 原题链接：https://leetcode.cn/problems/longest-increasing-subsequence/description/
 */
public class P300 {

    //最长递增子序列
    //dp[i]表示以第i个数为结尾的递增子序列的长度
    //dp[i]=max(dp[i],dp[j]+1)   (j<i, nums[i]>nums[j])
    public int lengthOfLIS(int[] nums) {
        int ans=1;
        int[] dp=new int[nums.length+1];
        for(int i=1;i<=nums.length;i++){
            dp[i]=1;
            for(int j=1;j<i;j++){
                if(nums[j-1]<nums[i-1]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            ans=Math.max(ans,dp[i]);
        }
        return ans;
    }
}
